//
//  ProblemOffer30.swift
//  LeetCode
//
//  Created by 武侠 on 2022/3/11.
//  Copyright © 2022 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 剑指 Offer 30. 包含min函数的栈 ✅
 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 示例:
     MinStack minStack = new MinStack();
     minStack.push(-2);
     minStack.push(0);
     minStack.push(-3);
     minStack.min();   --> 返回 -3.
     minStack.pop();
     minStack.top();   --> 返回 0.
     minStack.min();   --> 返回 -2.
 提示：
    各函数的调用总次数不超过 20000 次
 */
class ProblemOffer30 {
    /*
     列表A：存储正常插入和返回的栈
     数组B：存储当前最小的值，是一个递减队列
     push(x):
        listA: x直接插入到listA的尾部
        listB: 如果为空：x插入ListB中，
               不为空：判断listB的最后一个值是否>x, 如果>x，说明x是目前最小的值，<x, 说明x不是目前最小值，没必要存储
     pop:
        listA: 删除尾部的值x
        listB: 判断x是否==listB的最后一个值，如果相等说明x就是目前最小的值，需要从listB中删除
     */
    var listA: [Int] = []
    var listB: [Int] = []
    /** initialize your data structure here. */
    init() {
    }
    
    func push(_ x: Int) {
        listA.append(x)
        if listB.isEmpty || listB.last! >= x {
            listB.append(x)
        }
    }
    
    func pop() {
        if listA.isEmpty {
            return
        }
        let x = listA.removeLast()
        if listB.isEmpty == false, x == listB.last! {
            listB.removeLast()
        }
    }
    
    func top() -> Int {
        return listA.isEmpty ? -1 : listA.last!
    }
    
    func min() -> Int {
        return listB.isEmpty ? -1 : listB.last!
    }
}
